The inventor has proposed a technique of calculating f(x) for an input x using a randomizable sampler and a sampler described below (for example, refer to Non-patent literature 1).
R is defined as a random variable with a value in group G. What returns war′ corresponding to a sample r′ in accordance with the random variable R every time an integer a of 0 or more for wεG is given is referred to as a randomizable sampler with an error R for w. In the randomizable sampler, distribution of the random variable R is unrelated to the integer a.
In addition, what returns wr′ corresponding to the sample r′ in accordance with the random variable R every time a demand is received in wεG is referred to as a sampler with an error R for w.
The randomizable sampler and the sampler calculate war′ and wr′, respectively, using a function called black box.
In a case that, when r1 and r2 are realized values of the random variable R, an output f(x)ar1 of the randomizable sampler with an error R for f(x) is equal to the a-th power (f(x)r2)a of an output f(x)r2 of the sampler with an error R for f(x), r1 and r2 are unit elements eg of group G with high probability. Accordingly, since f(x)r2=f(x)eg=f(x) in this case, the output f(x)r2 of the sampler becomes f(x) intended to be obtained.